#include<vector>
#include<iostream>
using namespace std;
// 讲一个{a1,b1,a2,b2,a3,b3...}
// 变成{a1,a2,a3...}和{b1,b2,b3...}

// 链表声明
struct LinkedList
{
    LinkedList *next;
    int data;
    LinkedList() {
        this->data=-1;
        this->next=nullptr;
    };
    LinkedList(int data)
    {
        this->data = data;
        this->next = nullptr;
    }
    LinkedList(int data, LinkedList *next)
    {
        this->data = data;
        this->next = next;
    }
};

void showLinkedList(LinkedList *hair)
{
    auto temp = hair->next;
    while (temp != nullptr)
    {
        cout << "temp.val is " << temp->data << " " << endl;
        temp = temp->next;

    }
    cout << endl;
}

/// @brief 将一个链表拆分成两个
/// @param hair 带有头节点的链表
auto solution(LinkedList *hair)
{
    LinkedList *head1 = new LinkedList();//存储ai的头节点
    auto rear1 = head1;//因为需要保证ai是有序的，使用尾插法

    LinkedList *head2 = new LinkedList();//存储bi的头节点

    auto temp = hair->next;//临时节点，用来遍历链表

    //每次while循环，都会将一对（两个）节点同时插入，一个是ai，一个是bi
    while (temp){
        auto n = temp->next;//因为temp在插入到某个链中的时候，需要断开，所以先保存他的next
        temp->next = nullptr;//将这个待插入的节点，先断开

        //对ai的处理
        rear1->next = temp;//尾插法
        rear1 = rear1->next;
        temp = n;
        //对bi的处理，因为每次插入两个，可能遇到奇数个节点的情况
        //此时要判断temp是否为空
        if (temp != nullptr)//ai后面还有bi
        {
            //头插法
            auto n2 = temp->next;//和上面一样，需要保存temp的next
            temp->next = head2->next;
            head2->next = temp;
            temp = n2;
        }
        else//如果temp为空了，说明是奇数个节点，ai后面没有bi了，不再循环
            break;
    }

    hair=head1;//将原来的头，更新为ai的头
    return head2;//将bi的头返回
}

int main(void)
{
    auto hair = new LinkedList();
    auto head = new LinkedList(0, new LinkedList(1, new LinkedList(2, new LinkedList(3, new LinkedList(4,nullptr)))));
    hair->next = head;
    showLinkedList(hair);

    auto res=solution(hair);
    cout << "head1 is " << endl;
    showLinkedList(hair);
    cout << " head2 is " << endl;
    showLinkedList(res);
    return 0;
}